package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code54Trie {

    class Trie {

        class Node {
            int pass;
            int end;
            Node[] nexts;

            public Node() {
                nexts = new Node[26];
            }
        }

        private Node root;

        public Trie() {
            root = new Node();
        }

        public void insert(String word) {
            if (word == null || word.isEmpty()) {
                return;
            }
            char[] str = word.toCharArray();
            Node node = root;
            node.pass++;
            int path = 0;
            for (char c : str) {
                path = c - 'a';
                // 构造并去往下一个节点
                if (node.nexts[path] == null) {
                    node.nexts[path] = new Node();
                }
                node = node.nexts[path];
                node.pass++;
            }
            // 尾结点
            node.end++;
        }

        public boolean search(String word) {
            if (word == null || word.isEmpty()) {
                return false;
            }
            char[] str = word.toCharArray();
            Node node = root;
            int path = 0;
            for (char c : str) {
                path = c - 'a';
                if (node.nexts[path] == null) {
                    return false;
                }
                // 搜索下个节点
                node = node.nexts[path];
            }
            // 需完整匹配
            return node.end > 0;
        }

        public boolean startsWith(String prefix) {
            if (prefix == null || prefix.isEmpty()) {
                return false;
            }
            char[] str = prefix.toCharArray();
            Node node = root;
            int path = 0;
            for (char c : str) {
                path = c - 'a';
                if (node.nexts[path] == null) {
                    return false;
                }
                node = node.nexts[path];
            }
            return node.pass > 0;
        }
    }
}
